# coding: utf8
# datetime: 2021-04-02
# 题目地址: https://leetcode-cn.com/problems/volume-of-histogram-lcci/


from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        ret = 0
        stack = list()
        for index, height_ in enumerate(height):
            while stack and height[stack[-1]] < height_:
                min_index = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                currWeight = index-left-1
                currHeight = min(height[left], height[index])-height[min_index]
                ret += currHeight*currWeight
            stack.append(index)
        return ret

a = Solution()
print(a.trap([2,0,2]))
